package org.example.algorithm.linkedlist;

//148. 排序链表
//-1 5 3 4 0
public class SortListSolution {
    public static void main(String[] args) {
        ListNode node = new ListNode(4);
        node.next = new ListNode(2);
        node.next.next = new ListNode(1);
        node.next.next.next = new ListNode(3);
        SortListSolution solution = new SortListSolution();
        ListNode ans = solution.sortList(node);
        ListNode cur = ans;
        while (cur!=null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    public ListNode sortList(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        int len = getListLength(head);
        for (int i=1;i<len;i=i*2) {
            dummy.next = sortPart(dummy.next, i);
        }
        return dummy.next;
    }

    private ListNode sortPart(ListNode node, int partLen) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;

        ListNode remain = node;
        while (remain != null) {
            ListNode remainPart = getPart(remain, partLen);
            ListNode part1 = remain;
            remain = remainPart;
            ListNode remainPart2 = getPart(remain, partLen);
            ListNode part2 = remain;
            remain = remainPart2;
            ListNode[] mergeList = doMergeReturnStartAndEnd(part1, part2);
            tail.next = mergeList[0];
            tail = mergeList[1];
        }
        return dummy.next;
    }

    //获取一次分割长度的末尾及剩余部分开头
    private ListNode getPart(ListNode node, int partLen) {
        int i = 0;
        ListNode cur = node;
        while (i < partLen-1 && cur != null ) {
            cur = cur.next;
            i++;
        }
        ListNode partRemain = cur == null ? cur : cur.next;
        if (cur != null) {
            cur.next = null;
        }
        return partRemain;
    }

    private int getListLength(ListNode node) {
        int len = 0;
        ListNode cur = node;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        return len;
    }

    private ListNode[] doMergeReturnStartAndEnd(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                tail.next = node2;
                node2 = node2.next;
            } else {
                tail.next = node1;
                node1 = node1.next;
            }
            tail = tail.next;
        }
        tail.next = node1 == null ? node2 : node1;
        ListNode[] list = new ListNode[2];
        list[0] = dummy.next;
        ListNode cur = list[0];
        while (cur.next != null) {
            cur = cur.next;
        }
        list[1] = cur;
        return list;
    }

    public ListNode sortList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode[] parts = partition(head);
        return doMerge(sortList(parts[0]), sortList(parts[1]));
    }

    private ListNode doMerge(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                tail.next = node2;
                node2 = node2.next;
            } else {
                tail.next = node1;
                node1 = node1.next;
            }
            tail = tail.next;
        }
        tail.next = node1 == null ? node2 : node1;
        return dummy.next;
    }

    //双指针找中间位置作为分割点
    private ListNode[] partition(ListNode node) {
        ListNode slow = node;
        ListNode fast = node;
        ListNode[] ans = new ListNode[2];
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ans[0] = slow.next;
        slow.next = null;
        ans[1] = node;
        return ans;
    }
}
